﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0175_ReverseKGroup : IAlgorithm
    {
        // 25. K 个一组翻转链表

        // 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
        // k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
        // 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

        // 提示：
        //  链表中的节点数目为 n
        //  1 <= k <= n <= 5000
        //  0 <= Node.val <= 1000

        public void Test()
        {
            // 算法参数定义
            var head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
            // 算法执行与打印
            var res = ReverseKGroup(head, 1);
            while (res != null)
            {
                Console.Write(res.val + " ");
                res = res.next;
            }
        }

        // 算法
        public ListNode ReverseKGroup(ListNode head, int k)
        {
            if (k == 1) return head;

            var sentinelNode = new ListNode(0, head);
            var loopNode = sentinelNode;
            var nodeArray = new ListNode[k];
            while (loopNode.next != null)
            {
                nodeArray[0] = loopNode.next;
                for (int i = 1; i < k; i++)
                    if (nodeArray[i - 1].next == null)
                        return sentinelNode.next;
                    else
                        nodeArray[i] = nodeArray[i - 1].next;
                nodeArray[0].next = nodeArray[k - 1].next;
                loopNode.next = nodeArray[k - 1];
                for (int i = k; i >= 2; i--)
                    nodeArray[i - 1].next = nodeArray[i - 2];
                loopNode = nodeArray[0];
            }

            return sentinelNode.next;
        }

        public ListNode reverseKGroup(ListNode head, int k)
        {
            ListNode hair = new ListNode(0, head);
            ListNode pre = hair;
            while (head != null)
            {
                var tail = pre;
                // 查看剩余部分长度是否大于等于 k
                for (int i = 0; i < k; ++i)
                {
                    tail = tail.next;
                    if (tail == null) return hair.next;
                }
                ListNode nex = tail.next;
                ListNode[] reverse = myReverse(head, tail);
                head = reverse[0];
                tail = reverse[1];
                // 把子链表重新接回原链表
                pre.next = head;
                tail.next = nex;
                pre = tail;
                head = tail.next;
            }

            return hair.next;
        }

        public ListNode[] myReverse(ListNode head, ListNode tail)
        {
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail)
            {
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[] { tail, head };
        }
    }
}
